package org.example.order;

import ch.qos.logback.classic.filter.LevelFilter;

/**
 * <p>
 * Description:归并排序
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/14 15:54
 */
public class
MergeSort {

    public static void main(String[] args) {
        // 调用
        int[] nums = { 3, 4, 1, 5, 2, 1 };

        int[] temp = new int[nums.length];

        MergeSort m = new MergeSort();
//        m.mergeSort1(nums,0,nums.length - 1);

        m.mergeSort2(nums,0,nums.length - 1,temp);

        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    /**
     * 解决方案 1
     * @param nums 要排序的数组
     * @param l 左指针
     * @param r 右指针
     */
    public void mergeSort1(int[] nums,int l,int r){
       if(l >= r){
           return;
       }
       int m = (l + r) / 2;
       mergeSort1(nums,l,m);
       mergeSort1(nums,m + 1,r);
       int[] tmp = new int[r - l + 1];
        for (int i = l; i <= r ; i++) {
            tmp[i - l] = nums[i];
        }

        int i = 0,j = m - l + 1;
        for (int k = l; k <= r ; k++) {
            if(i == m - l + 1){
                nums[k] = tmp[j++];
            }else if(j == r - l + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                nums[k] = tmp[j++];
            }
        }
    }

    public void mergeSort2(int[] nums,int start,int end,int[] temp){
        if(start >= end){
            return;
        }
        int m = (start + end) / 2;
        mergeSort2(nums,start,m,temp);
        mergeSort2(nums,m+1,end,temp);

        merge(nums,start,m,end,temp);
    }

    public void merge(int[] nums,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else{
                temp[t++] = nums[j++];
            }
        }

        while (i <= mid){
            temp[t++] = nums[i++];
        }
        while (j <= right){
            temp[t++] = nums[j++];
        }
        t = 0;
        while (left <= right){
            nums[left++] = temp[t++];
        }
    }
}
